class Solution {
    public int divide(int a, int b) {
        //Integer.MAX_VALUE/Integer.MIN_VALUE的用法/在一堆数字里找最大值和最小值的简单方法
        //在JDK中，整形类型是有范围的，最大值为Integer.MAX_VALUE，即2147483647，
        //最小值为Integer.MIN_VALUE -2147483648。对整形最大值加1，2147483648（越界了），
        //那么此时值为多少呢？结果是-2147483648，即是Integer.MIN_VALUE。
        //Integer.MAX_VALUE + 1 = Integer.MIN_VALUE
        if(b == 1) {
            return a;
        }
        if(b == -1) {
            return a == Integer.MIN_VALUE ? Integer.MAX_VALUE : -a;
        }
        if(a == 0) {
            return 0;
        }
        boolean positive = (a ^ b) >= 0;//异或判断正负

        //为避免溢出，都转为负数
        a = a < 0 ? a : -a;
        b = b < 0 ? b : -b;

        //快速相减
        int quotient = 0;//商
        while (a <= b){
            int base = 1;
            int divisor = b;
            //使用减法, 避免溢出
            while (a - divisor <= divisor){//a与b(divisor)都是负数，a-b判断之后是否还小于被除数
                //a-b差值还小于商时，a至少是b的2倍，除数左移一位（乘2），商至少是上次值得2倍，左移一位
                divisor <<= 1;
                base <<= 1;
            }
            quotient += base;
            a -= divisor;
        }
        return positive ? quotient : -quotient;
    }
}